// 邻接表，表示图
// 对于有向图，有入度（in-degree）和出度（out-degree）入度是指指向该节点的边的数量，出度是指从该节点出发指向其他节点的边的数量。
// 顶点 表节点
class Vertex {
  /**
   * @description:
   * @param {*} data记录顶点节点的数值
   * @return {*}
   */
  constructor(data) {
    this.data = data; // 顶点域
    this.firstEdge = null; // 指向第一个邻接边的指针，指向当前顶点的边表中的第一个节点
    this.outNum = 0; // 在无向图中表示与顶点邻接的边的数量，在有向图中为出度
    this.inNum = 0; // 在有向图中为顶点的入度
  }
}
// 边 表节点
class Edge {
  constructor(data, weight = 0, nextEdge = null) {
    this.data = data; // 邻接点域
    this.nextEdge = nextEdge; // 指向下一条邻接边
    this.weight = weight; // 权重
  }
}

// 创建图
class Graph {
  constructor(isDirect) {
    this.eNum = 0; // 边的数目
    this.adj = []; // 顶点表
    this.isDirect = isDirect; // 是否是有向图
  }
  // 初始化顶点表
  initVertex(verArr) {
    for (let i = 0; i < verArr.length; i++) {
      let newVer = new Vertex(verArr[i]);
      this.adj[i] = newVer;
    }
  }

  // 插入新的顶点
  insertVertex(x) {
    // 创建新顶点
    let newVer = new Vertex(x);
    // 添加到当前的顶点表
    this.adj.push(newVer);
  }

  // 找到节点x在adj中所在的位置
  // 前面加上下划线表示不应该在具体实例中调用该方法
  _find(x) {
    let pos = -1;

    for (let i = 0; i < this.adj.length; i++) {
      if (x == this.adj[i].data) pos = i;
    }

    return pos;
  }

  // 判断图中是否存在边(x,y)或者<x, y>。
  //从顶点x的边表第一元素开始遍历，如果发现存在y节点则说明顶点x和顶点y之间已经有了一条边
  hasEdge(x, y) {
    let pos = this._find(x);
    if (pos > -1) {
      // 找出顶点的第一条边
      let curVer = this.adj[pos].firstEdge;

      if (!curVer) {
        // 没有与顶点x的邻接点
        return false;
      } else {
        // 至少有一个节点与顶点x是相邻的
        // 遍历顶点的所有邻接节点
        while (curVer) {
          // 如果相等，说明存在边
          if (curVer.data === y) return true;

          curVer = curVer.nextEdge;
        }

        return false;
      }
    }
  }

  // 向图中插入边(x, y)或者边<x, y>
  /**
   1.连接任意顶点，分为有向图还是无向图，
    如果是无向图的话，在插入边(x, y)后还要再插入边(y, x)，因为用邻接表来存储无向图时，顶点x的边表中具有顶点y，那么顶点y的边表中必然也有顶点x。
    如果是有向图中的话，只需要插入边<x, y>就可以
   2.在插入边的时候，首先判断下顶点x和顶点y之间是否已经存在了一条边了，只有x和y之间没有边时，才可以在顶点x和顶点y之间插入一条边
   3.在插入边的过程中，如果是有向图时，同时更新每个顶点的入度和出度，而如果是无向图的话，则分别更新了与x和y相邻的节点的数量。
   */
  addEdge(x, y, w = 0) {
    let posX = this._find(x);
    let posY = this._find(y);
    let newEdgeX = new Edge(x, w);
    let newEdgeY = new Edge(y, w);
    // 如果是无向图，在插入边(x, y)时还要插入边(y, x)
    if (!this.isDirect) {
      // <x, y>或者<y, x>边不存在
      if (!this.hasEdge(x, y) && !this.hasEdge(y, x)) {
        // 如果顶点x在顶点表中
        if (posX > -1) {
          // 取出顶点x的第一条边
          let curVer = this.adj[posX].firstEdge;
          // 如果第一条边不存在
          if (!curVer) {
            // 创建第一条边
            this.adj[posX].firstEdge = newEdgeY;
            // outNum无向图中，表示顶点邻接边的数量
            this.adj[posX].outNum++;
          } else {
            let len = this.adj[posX].outNum - 1;
            // x点的邻接边存在，往所有边之后追加边
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeY;
            // 邻接边数量+1
            this.adj[posX].outNum++;
          }
        }
        // 如果顶点y在顶点表中
        if (posY > -1) {
          // 取出顶点y的第一条边
          let curVer = this.adj[posY].firstEdge;
          if (!curVer) {
            this.adj[posY].firstEdge = newEdgeX;
            this.adj[posY].outNum++;
          } else {
            let len = this.adj[posY].outNum - 1;
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeX;
            this.adj[posY].outNum++;
          }
        }
        // 边的数量+1
        this.eNum++;
      }
    }
    // 有向图， 只用处理<x, y>方向的边
    else {
      if (!this.hasEdge(x, y)) {
        // 如果顶点x在顶点表中
        if (posX > -1) {
          // x顶点的第一条边
          let curVer = this.adj[posX].firstEdge;
          // 如果当前顶点没有第一个边节点
          if (!curVer) {
            this.adj[posX].firstEdge = newEdgeY;
            // x顶点的出度+1
            this.adj[posX].outNum++;
          } else {
            let len = this.adj[posX].outNum - 1;
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeY;
            // 顶点x的出度+1
            this.adj[posX].outNum++;
          }
        }
        // 如果顶点x在顶点表中
        if (posY > -1) {
          let curVer = this.adj[posY];
          // 顶点y的入度增长
          curVer.inNum++;
        }
      }
    }
  }

  // 在图中删除边(x, y)或者边<x, y>
  // 在无向图中删除边(x, y)时，同时也需要删除(y, x)，有向图则只需要删除边<x, y>就可以
  // 由于是由邻接表表示的数据结构，当删除边(x, y)时也需要同时删除边(y, x);
  removeEdge(x, y) {
    //在图中删除边(x, y)
    if (this.hasEdge(x, y)) {
      let posX = this._find(x); //查找x顶点
      let posY = this._find(y); //查找y顶点
      let curVerX = this.adj[posX].firstEdge; // x的第一条边
      let curVerY = this.adj[posY].firstEdge; //y的第一条边
      // 首先是无向图，当删除边(x, y)时也需要同时删除边(y, x)
      if (!this.isDirect) {
        // 删除边(x, y)
        // 如果顶点的第一个节点即是要找的节点
        if (curVerX.data === y) {
          // 删除第一条边，把顶点x的nextEdge作为第一条边
          this.adj[posX].firstEdge = curVerX.nextEdge;
          this.adj[posX].outNum--;
          curVerX = null;
        }
        // curVerX如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerX) {
          let preVerX = curVerX;
          // 继续查找下一条边
          curVerX = curVerX.nextEdge;
          if (curVerX && curVerX.data === y) {
            preVerX.nextEdge = curVerX.nextEdge;
            this.adj[posX].outNum--;
            curVerX = null;
          }
        }
        // 删除边(y, x)
        // 如果顶点的第一个节点即是要找的节点
        if (curVerY.data === x) {
          // 把y顶点的下一条边赋值给第一条边
          this.adj[posY].firstEdge = curVerY.nextEdge;
          this.adj[posY].outNum--;
          curVerY = null;
        }
        //curVerY如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerY) {
          let preVerY = curVerY;
          curVerY = curVerY.nextEdge;
          if (curVerY && curVerY.data === x) {
            preVerY.nextEdge = curVerY.nextEdge;
            this.adj[posY].outNum--;
            curVerY = null;
          }
        }
      } else {
        // 删除边<x, y>
        // 如果顶点的第一个节点即是要找的节点
        if (curVerX.data === y) {
          this.adj[posX].firstEdge = curVerX.nextEdge;
          this.adj[posX].outNum--;
          curVerX = null;
        }
        // curVerX如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerX) {
          let preVerX = curVerX;
          curVerX = curVerX.nextEdge;

          if (curVerx && curVerX.data === y) {
            preVerX.nextEdge = curVerX.nextEdge;
            this.adj[posX].outNum--;
            curVerX = null;
          }
        }
        this.adj[posY].inNum--;
      }
      this.eNum--;
    }
  }

  // 从图中删除顶点x,与删除边操作不同
  //在删除图中的一个顶点时，与此顶点所有相邻的边都要删除。
  //   两步操作，第一步删除所有以x为起点的边，第二步删除所有以x为终点的边
  deleteVertex(x) {
    let pos = this._find(x);
    if (pos > -1) {
      // 删除从x出发的边
      let curVer = this.adj[pos].firstEdge;
      while (curVer) {
        this.removeEdge(x, curVer.data);
        curVer = curVer.nextEdge;
      }
      // 删除终点是x的边
      for (let i = 0; i < this.adj.length; i++) {
        let temVer = this.adj[i].firstEdge;

        while (temVer) {
          if (temVer.data === x) {
            this.removeEdge(this.adj[i].data, temVer.data);
          }
          temVer = temVer.nextEdge;
        }
      }
      // 删除顶点x
      this.adj.splice(pos, 1);
    }
  }

  // 与顶点x邻接的所有节点
  //   不断的遍历每个顶点的边
  allNeightbors(x) {
    let pos = this._find(x);

    if (pos > -1) {
      let result = `${x}`;
      let curVer = this.adj[pos].firstEdge;

      while (curVer) {
        result += `=>${curVer.data}`;
        curVer = curVer.nextEdge;
      }

      console.log(result);
    }
  }

  // 获得图中最小的权值
  getMinEdgeWeight() {
    let minWeight = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i < this.adj.length; i++) {
      let curVer = this.adj[i].firstEdge;

      while (curVer) {
        if (minWeight > curVer.weight) {
          minWeight = curVer.weight;
        }

        curVer = curVer.nextEdge;
      }
    }

    return minWeight;
  }

  // 广度优先求出图中所有的连通分量，从给定的顶点x开始
  BFSTraverse(x = this.adj[0].data) {
    // 访问过的标记数组，标记数组和顶点表 相关联的是下标
    let visited = [];
    let result = "";
    for (let i = 0; i < this.adj.length; i++) {
      visited[i] = false;
    }
    // 求以x为起始点的连通分量, 第一次A
    result = this._BFS(x, visited);
    // 如果有还未被访问过的顶点，则从该顶点继续遍历
    for (let i = 0; i < visited.length; i++) {
      if (!visited[i]) {
        let x = this.adj[i].data;
        result += `&${this._BFS(x, visited)}`; // 其他的连通分量
      }
    }
    return result;
  }

  // 实际进行广度遍历的函数，每次遍历都是 获得一个以顶点x为起点的连通分量
  _BFS(x, visited) {
    let result = "";
    let queue = [];
    let pos = this._find(x);
    if (pos > -1) {
      result += `${x}`;
      visited[pos] = true;
      // 获取到当前顶点
      let curVer = this.adj[pos];
      // 顶点x入队列
      queue.push(curVer);
      while (queue.length) {
        // 取出队列的第一个值
        curVer = queue.shift();
        // 回到顶点的表中，再次计算
        pos = this._find(curVer.data);
        curVer = this.adj[pos].firstEdge; // 第一次是 A - B
        //检测顶点的所有邻接点
        while (curVer) {
          pos = this._find(curVer.data);
          // 如果当前顶点未被访问过
          if (!visited[pos]) {
            result += `->${curVer.data}`;
            // 标记未已经访问过
            visited[pos] = true;
            queue.push(curVer);
          }
          curVer = curVer.nextEdge;
        }
      }
    }
    return result;
  }

  // 深度优先求出图中所有的连通分量，从给定的顶点x开始
  DFSTraverse(x) {
    let result = "";
    let visited = [];
    for (let i = 0; i < this.adj.length; i++) {
      visited[i] = false;
    }
    result = this._DFS(x, visited);
    // 如果还有未被访问过的顶点，则以该顶点再次出发
    for (let i = 0; i < visited.length; i++) {
      if (!visited[i]) {
        let x = this.adj[i].data;
        result += `&${this._DFS(x, visited)}`;
      }
    }
    return result;
  }

  // 实际进行深度遍历的函数，每次遍历都是得到 以顶点x为起点的连通分量
  _DFS(x, visited) {
    let result = "";
    let stack = []; // 辅助堆栈
    let pos = this._find(x);
    let curVer = this.adj[pos]; // 根据给的x值找到具体的顶点
    if (pos > -1) {
      stack.push(curVer); // 顶点x入栈
      result += `${x}`;
      // 访问过的顶点，做标记
      visited[pos] = true;
      while (stack.length) {
        // 获取栈顶元素,不能使用pop，pop会把节点删除
        curVer = stack[stack.length - 1];
        // 获取栈顶元素在顶点表中的位置
        pos = this._find(curVer.data);
        // 获取顶点的第一个邻接点
        curVer = this.adj[pos].firstEdge;
        // 邻接点存在
        while (curVer) {
          pos = this._find(curVer.data);

          if (visited[pos]) {
            // 如果该节点已经访问过了,则访问该节点的下一个相邻的节点
            curVer = curVer.nextEdge;
          } else {
            stack.push(curVer);
            result += `->${curVer.data}`;
            visited[pos] = true;
            break;
          }
        }
        // 如果顶点的所有邻接点都访问过
        if (!curVer) stack.pop();
      }
    }
    return result;
  }

  //========最小生成树============
  /* 
  在求最小生成树之前，还有一些准备工作要做:
    获取图中边的权值
    判断给定的图是否是一幅连通图
    获取图中的权值之和
    获取图中所有的边
  */
  // 获取边(x, y)或<x, y>对应的权值
  getEdgeWeight(x, y) {
    let pos = this._find(x);
    if (pos > -1) {
      let curVer = this.adj[pos].firstEdge;
      while (curVer) {
        if (curVer.data === y) return curVer.weight;
        curVer = curVer.nextEdge;
      }
      return 0;
    }
  }

  // 判断当前的图是否是连通图
  isConnected(x = this.adj[0].data) {
    // 任选一个点作为顶点
    let len = this.adj.length;
    let visited = new Array(len); // 把所有点都有进行记录，后边判断是否还有未被访问的点时使用
    for (let i = 0; i < len; i++) {
      visited[i] = false;
    }
    this._BFS(x, visited);
    // 如果遍历一边之后仍有顶点未被访问，则该图不是连通的
    for (let i = 0; i < len; i++) {
      if (!visited[i]) return false;
    }
    return true;
  }

  // 获得图中权重之和
  getSumOfWeight() {
    // 当图不是连通的时候，获取权重之和没有意义
    if (!this.isConnected()) return;
    let sum = 0;
    let vertex = this.adj;
    if (!this.isDirect) {
      // 如果是无向图
      for (let i = 0; i < vertex.length - 1; i++) {
        for (let j = i; j < vertex.length; j++) {
          let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);

          if (weight) sum += weight;
        }
      }
    } else {
      for (let i = 0; i < vertex.length; i++) {
        for (let j = 0; j < vertex.length; j++) {
          let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);

          if (weight) sum += weight;
        }
      }
    }
    return sum;
  }

  // 普里姆算法
  getPrimMSTree() {
    // 不是连通图时求最小生成树没有意义
    if (!this.isConnected) return;
    let V = this.adj; // 顶点集V
    let Vt = [V[0]]; // 添加任意一个顶点
    let VVt = V.filter((x) => Vt.indexOf(x) === -1); // VVt = V - Vt, 出去Vt点的其他点集合
    //初始化空图
    let MinTree = new Graph(this.isDirect);
    // 将点集合，插入到树中
    V.forEach((x) => MinTree.insertVertex(x.data));
    // 若树中不含全部顶点
    while (Vt.length !== V.length) {
      //当找到权值最小的边时，m VT是边的一个顶点
      let mVt = null;
      //当找到权值最小的边时，m V_VT是边的另一个顶点
      let mVVt = null;
      // 最小权重值，先将minW赋个极大的数值
      let minW = Number.MAX_SAFE_INTEGER;
      // 在VT和V_VT中找到边中的最小权值
      // 从VT中取出一个顶点
      for (let i = 0; i < Vt.length; i++) {
        // 从VVt中取出一个顶点
        for (let j = 0; j < VVt.length; j++) {
          // 获取Vt-VVt之间的权重值
          let weight = this.getEdgeWeight(Vt[i].data, VVt[j].data);
          // 权重值weight小于最小值
          if (weight && minW > weight) {
            // 更新最小值
            minW = weight;
            mVt = Vt[i];
            mVVt = VVt[j];
          }
        }
      }
      Vt.push(mVVt);
      MinTree.addEdge(mVt.data, mVVt.data, minW);
      VVt = V.filter((x) => Vt.indexOf(x) === -1);
    }
    return MinTree;
  }

  // 获取图中所有的边
  getAllEdges() {
    let vertex = this.adj; // 图中的所有顶点
    let edges = []; // 在edges中存放图中所有的边

    // 如果是无向图
    if (!this.isDirect) {
      for (let i = 0; i < vertex.length - 1; i++) {
        for (let j = i; j < vertex.length; j++) {
          // 判断2个点之间是否有边
          if (this.hasEdge(vertex[i].data, vertex[j].data)) {
            let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);
            edges.push([vertex[i].data, vertex[j].data, weight]);
          }
        }
      }
    }
    // 如果有向图
    else {
      for (let i = 0; i < vertex.length; i++) {
        for (let j = 0; j < vertex.length; j++) {
          if (this.hasEdge(vertex[i].data, vertex[j].data)) {
            let weight = this.getEdgeWeight(vertex[i].data, vertex[j].data);
            edges.push([vertex[i].data, vertex[j].data, weight]);
          }
        }
      }
    }
    // 在edges数组中，每一个元素都是一个数组，该数组一共三个元素
    // 顶点x的值，顶点y的值，和顶点x和y构成的边上的权值
    return edges;
  }

  // 克鲁斯卡尔算法
  //   算法的基本思想是先找权重最小的边，再找权重次小的边
  getKruskalMSTree() {
    // 不是连通图时求最小生成树没有意义
    if (!this.isConnected()) return;
    let V = this.adj; // 顶点集V
    let numS = V.length; // 树中的连通分量
    let E = this.getAllEdges(); // 在E中存放图中所有的边
    let mEdge = null;
    let MSTree = new Graph(this.isDirect); // 初始化空树
    V.forEach((x) => MSTree.insertVertex(x.data)); // 树中只有顶点
    while (numS > 1) {
      let minWeight = Number.MAX_SAFE_INTEGER;
      // 从图中取出权值最小的边<u, v>
      for (let i = 0; i < E.length; i++) {
        if (E[i][2] < minWeight) {
          mEdge = E[i];
          minWeight = E[i][2];
        }
      }
      //广度优先遍历
      let result = MSTree.BFSTraverse(mEdge[0]);
      //只取&前面的字符串
      result = result.split("&")[0];
      let pos = result.indexOf(mEdge[1]);
      // 如果u和v属于树中不同的连通分量，就将此边加入生成树中
      // 从顶点mEdge[0]遍历一遍发现没有mEdge[1]，说明两个顶点不在一个连通分量之中
      if (pos === -1) {
        MSTree.addEdge(mEdge[0], mEdge[1], mEdge[2]);
        numS--;
      }
      // 去掉E中权值最小的边
      E = E.filter((x) => x !== mEdge);
    }
    return MSTree;
  }

  /**
   * 求带权图顶点x到其他顶点的最短路径
   * 从x到y可能有多条路径，把带权路径长度最短的那条路径称为最短路径
   * 求解最短路径的算法通常都依懒于一种性质，
   * 也就是两点之间的最短路径也包含了路径上的其他顶点间的最短路径
   * @param {*} x
   */
  // x点到其他各个点最短路径
  getShortestPath(x) {
    // 使用Dijkstra算法，
    // 如果是无向图或者边有负的权值时退出
    // 如果x不存在于图中时退出
    // 如果从顶点x到不了图中任意一个顶点则退出
    if (
      !this.isDirect ||
      this.getMinEdgeWeight() < 0 ||
      this._find(x) === -1 ||
      !this.isConnected(x)
    ) {
      return -1;
    }

    var MAX = Number.MAX_SAFE_INTEGER;

    // 初始化
    var len = this.adj.length;

    // 在dist数组中，dist[i]的初值为顶点x到顶点i之间的权值，
    // x到i没有路径时，dist[i]记为无穷大
    var dist = [];
    var path = []; // path[i]表示顶点x到i的最短路径
    var vers = []; // 顶点集
    var exts = [x]; // 已找到最短路径的点的集合

    // 初始化path和dist数组
    for (let i = 0; i < len; i++) {
      vers[i] = this.adj[i].data;
      dist[i] = this.getEdgeWeight(x, vers[i]) || MAX;
      if (dist[i] !== MAX) {
        path[i] = `${x}->${vers[i]}`;
      } else {
        path[i] = "";
      }
    }

    var rem = vers.filter((x) => exts.indexOf(x) === -1); // 剩余的顶点
    var n = 1;

    while (n < len) {
      // 在dist中寻找最小值
      var min = MAX;
      var idx = -1;

      for (let i = 0; i < len; i++) {
        if (min > dist[i]) {
          min = dist[i];
          idx = i;
        }
      }

      var Vj = vers[idx]; // 直接找到Vj
      dist[idx] = MAX;
      exts.push(Vj);
      rem = vers.filter((x) => exts.indexOf(x) === -1);

      console.log(path[idx]); // 输出最短路径

      // 松弛工作
      for (let i = 0; i < rem.length; i++) {
        // Vj到其他节点的距离
        var w = this.getEdgeWeight(Vj, rem[i]) || MAX;
        var k = vers.indexOf(rem[i]);

        if (w + min < dist[k]) {
          dist[k] = w + min;
          path[k] = `${path[idx]}->${rem[i]}`;
        }
      }

      n++;
    }
  }
}

/* let arr = ["A", "B", "C", "D", "E"];
let myGraph = new Graph(0);
myGraph.initVertex(arr);
myGraph.addEdge("A", "B", 5);
myGraph.addEdge("A", "C", 7);
myGraph.addEdge("A", "E", 6);
myGraph.addEdge("B", "E", 4);
myGraph.addEdge("C", "E", 2);
myGraph.addEdge("D", "B", 2);
myGraph.addEdge("D", "C", 4);
myGraph.addEdge("D", "E", 3); */
var arr = ["A", "B", "C", "D", "E"];
var myGraph = new Graph(1); // 1表示有向图
myGraph.initVertex(arr);

myGraph.addEdge("A", "B", 10);
myGraph.addEdge("A", "C", 3);
myGraph.addEdge("B", "C", 1);
myGraph.addEdge("B", "D", 2);
myGraph.addEdge("C", "B", 4);
myGraph.addEdge("C", "D", 8);
myGraph.addEdge("C", "E", 2);
myGraph.addEdge("D", "E", 7);
myGraph.addEdge("E", "D", 9);
for (let i = 0; i < arr.length; i++) {
  myGraph.allNeightbors(arr[i]);
}

myGraph.getShortestPath("A");

// for (let i = 0; i < arr.length; i++) {
//   myGraph.allNeightbors(arr[i]);
// }
// // 断开c和、e的连接
// myGraph.removeEdge("C", "E");
// for (let i = 0; i < arr.length; i++) {
//   myGraph.allNeightbors(arr[i]);
// }
// for (let i = 0; i < arr.length; i++) {
//   console.log(myGraph.BFSTraverse(arr[i]));
// }
// for (let i = 0; i < arr.length; i++) {
//   console.log(myGraph.DFSTraverse(arr[i]));
// }

// 普里姆算法
// let MSTree = myGraph.getPrimMSTree();
// console.log(MSTree.BFSTraverse()); // 广度优先遍历下看看
// 输出A->B->D->E->C
// console.log(MSTree.DFSTraverse()); // 深度优先遍历下看看
// 输出A->B->D->E->C
// console.log(MSTree.getSumOfWeight());
// 输出12

//克里斯卡尔算法
// let MSTree = myGraph.getKruskalMSTree();
// console.log(MSTree.BFSTraverse());
// console.log(MSTree.DFSTraverse());
// console.log(MSTree.getSumOfWeight());
